1. Field of the Invention
Aspects of the present invention relate to Automatic Repeat reQuest (ARQ) in a wireless communication system. More particularly, aspects of the present invention relate to techniques for advanced ARQ buffer management in a wireless communication system.
2. Description of the Related Art
According to a channel status of a radio resource, a wireless communication system may encounter an error in data transmitted and received. Hence, the wireless communication system may control or restore the data error using an Automatic Repeat reQuest (ARQ) scheme to raise transmission reliability.
Using the ARQ scheme, an ARQ receiver informs an ARQ transmitter of whether an ARQ block of data (hereafter referred to as an AQR block) is successfully received from the ARQ transmitter. For example, when the ARQ block received from the ARQ transmitter is free from error, the ARQ receiver transmits an ACKnowledge (ACK) to the ARQ transmitter. When the ARQ block received from the ARQ transmitter is corrupt, the ARQ receiver transmits a Negative ACK (NACK) to the ARQ transmitter. Herein, a series of operations of the ARQ receiver for transmitting the reception success or failure of the ARQ block to the ARQ transmitter is referred to as ARQ feedback.
Accordingly, the ARQ transmitter may acquire a reception status of the ARQ block transmitted to the ARQ receiver based on the ACK/NACK received from the ARQ receiver. When receiving the ACK from the ARQ receiver, the ARQ transmitter transmits a new ARQ block to the ARQ receiver. In contrast, when receiving the NACK information from the ARQ receiver, the ARQ transmitter retransmits the ARQ bock corresponding to the NACK to the ARQ receiver.
The ARQ scheme may be implemented differently for different wireless communication standards. An example of an ARQ transmission scheme utilized in the in the Institute of Electrical and Electronics Engineers (IEEE) 802.16e and the IEEE 802.16m standards is described below with reference to FIG. 1.
FIG. 1 illustrates an ARQ transmitter state machine for an ARQ block according to the related art.
Referring to FIG. 1, communication of an ARQ block may be in one of five states, namely a not-sent state 110, an outstanding state 120, a discarded state 130, a waiting-for-retransmission state 140, and a done state 150. Each ARQ enabled connection has an independent ARQ state machine. The minimum unit of an ARQ state transition is an ARQ block. An ARQ block begins at the not-sent state 110 before the ARQ block is initially transmitted.
When the ARQ block is transmitted, an ARQ_BLOCK_LIFETIME timer is initiated for the ARQ block and the ARQ block state transitions from the not-sent state 110 to the outstanding state 120 in step 112. When this occurs, an ARQ_TX_NEXT_SN parameter is incremented by one.
While the ARQ block is in the outstanding state 120, the ARQ transmitter waits for one of an ACK and a NACK from the corresponding ARQ receiver. If the ACK arrives, the ARQ block state transitions to the done state 150 in step 125. If the NACK arrives, the ARQ block state transitions to the waiting-for-retransmission state 140 in step 124. After the ARQ_BLOCK_LIFETIME period expires, the ARQ block state transitions to the discard state 130 in step 123.
While the ARQ block is in the waiting-for-retransmission state 140, the ARQ transmitter prepares for retransmission of the ARQ data corresponding to the ARQ block. If an ACK arrives, the ARQ block state transitions to the done state 150 in step 145. If the ARQ data corresponding to the ARQ block is re-transmitted, the ARQ block state transitions back to the outstanding state 120 in step 142. After the ARQ_BLOCK_LIFETIME timer expires, the ARQ block state transitions to the discard state 130 in step 143 without being retransmitted.
While the ARQ block is in the discard state 130, the ARQ transmitter sends a discard message and waits for an ACK from the ARQ receiver. If an ACK for the discard message or the ARQ block arrives, the ARQ block state transitions to the done state 150 in step 135.
When the ARQ block is in the done state 150, the ARQ transmitter completes the ARQ operation by erasing all the timers and ARQ state variables related to the ARQ block.
Each ARQ transmitter maintains an ARQ transmitting window with two parameters, namely an ARQ_TX_WINDOW_START parameter and the ARQ_TX_NEXT_SN parameter. The ARQ state machine regards all ARQ blocks up to ARQ_TX_WINDOW_START−1 as being acknowledged by the corresponding ARQ receiver. The ARQ_TX_WINDOW_START parameter represents the lower edge of the ARQ window in the ARQ transmitter. When the corresponding ARQ block of the ARQ_TX_WINDOW_START parameter in the ARQ state machine transitions to the done state 150, the ARQ_TX_WINDOW_START parameter moves to the next lowest ARQ Sequence Number (SN) that is not acknowledged by the ARQ receiver. The ARQ_TX_NEXT_SN parameter corresponds to the lowest SN which is the next ARQ block to be sent by the ARQ transmitter. The ARQ_TX_NEXT_SN parameter shall be within the interval from ARQ_TX_WINDOW_START to ARQ_TX_WINDOW_START+ARQ_WINDOW_SIZE.
Each ARQ receiver maintains an ARQ receiving window with two parameters, namely an ARQ_RX_WINDOW_START parameter and an ARQ_RX_HIGHEST_SN parameter. The ARQ state machine regards all ARQ blocks up to ARQ_RX_WINDOW_START−1 as being received. The ARQ_RX_WINDOW_START parameter represents the lower edge of ARQ window in the ARQ receiver. When the corresponding ARQ block of ARQ_RX_WINDOW_START is received correctly or after the expiration of an ARQ_RX_PURGE_TIMEOUT timer, ARQ_RX_WINDOW_START moves to the next lowest ARQ SN which is not received.
The ARQ_RX_HIGHEST_SN parameter corresponds to the ARQ SN of the highest ARQ block received, plus one. The ARQ_RX_HIGHEST_SN parameter shall be within the interval from ARQ_RX_WINDOW_START to ARQ_RX_WINDOW_START+ARQ_WINDOW_SIZE.
An example of an ARQ reception scheme utilized in the in the IEEE 802.16e and the IEEE 802.16m standards is described below with reference to FIG. 2.
FIG. 2 illustrates a flowchart for reception of an ARQ block according to the related art.
Referring to FIG. 2, when a Media Access Control (MAC) Packet Data Unit (PDU) is received in step 202, the AQR receiver checks a Fragmentation and Packing Extended Header (FPEH) and obtains ARQ block information for ARQ reception. After the ARQ receiver knows an ARQ SN and corresponding ARQ block, an ARQ receiver state machine adds the SN to the list of SNs to be acknowledged in step 204. The ARQ receiver state machine checks the validity of the SN by determining if the SN falls within the ARQ receiver window range (i.e., from ARQ_RX_WINDOW_START to ARQ_RX_WINDOW_START+ARQ_WINDOW_SIZE) in step 206. If an ARQ block is not valid (i.e., the ARQ block is not within the ARQ receiver window range), the receiver discards the ARQ block in step 208.
If ARQ SN is valid (i.e., the ARQ block is within the ARQ receiver window range), it is determined if the corresponding ARQ block is already received in step 210. If it is determined that the ARQ block is already received, the ARQ receiver state machine resets an ARQ_RX_PURGE_TIMEOUT timer in step 212 and discards the ARQ block in step 208. Here, the corresponding ARQ block is discarded because it is a duplicate block which should not be stored in a buffer. However, if it is determined that the ARQ block is not duplicated, the ARQ receiver state machine begins a procedure to update ARQ state variables and related timers in steps 214-224 and store the ARQ block in the buffer in step 226.
More specifically, if it is determined that the ARQ block is not duplicated, it is determined if the SN is greater than or equal to ARQ_RX_HIGHEST_SN in step 214. If it is determined that the SN is less than ARQ_RX_HIGHEST_SN, the procedure proceeds to step 218. However, if it is determined that the SN is greater than or equal to ARQ_RX_HIGHEST_SN, the ARQ receiver updates ARQ_RX_HIGHEST_SN as SN+1 in step 216 and proceeds to step 218.
In step 218, it is determined if SN is equal to ARQ_RX_WINDOW_START. If it is determined that SN is equal to ARQ_RX_WINDOW_START, ARQ_RX_WINDOW_START is advanced to the next lowest numbered ARQ block that has not been received in step 220, ARQ_SYNC_LOSS_TIMEOUT is reset in step 222 and the ARQ block is stored in step 226. However, if it is determined that the SN is not equal to ARQ_RX_WINDOW_START, the ARQ receiver marks the block as received and resets the ARQ_RX_PURGE_TIMEOUT timer for this SN in step 224. The ARQ block is then stored in step 226.
The ARQ receiver sends ARQ feedback using an ARQ feedback Information Element (IE) to update ARQ block reception status when an ARQ feedback poll is received from the ARQ transmitter or when an ARQ block has been missing for amount of time corresponding to DELIVERY_IN_ORDER_TIMEROUT.
When the ARQ transmitter receives the ARQ feedback IE, which does not include a selective ACK MAP, the ARQ transmitter considers all ARQ blocks in the interval ARQ_TX_WINDOW_START to SN (inclusive) as acknowledged, and sets ARQ_TX_WINDOW_START to SN+1. When the ARQ feedback IE includes the selective ACK MAP, the ARQ transmitter considers all ARQ blocks in the interval ARQ_TX_WINDOW_START to SN (not inclusive) as acknowledged, and sets ARQ_TX_WINDOW_START to SN. The Most Significant Bit (MSB) of the selective ACK MAP indicates an SN in ARQ feedback IE, which shall start from a NACK, and contiguous bits in the selective ACK MAP may be marked as an ACK or a NACK. The ARQ transmitter only considers valid ACKs within the ARQ window (i.e., ARQ_TX_WINDOW_START+ARQ_WINDOW_SIZE). ACKs outside the ARQ widow are ignored by the ARQ transmitter.
When a discard message is received from the ARQ transmitter, the ARQ receiver sends an ACK to the ARQ transmitter and discards the corresponding blocks in the discard message. The ARQ_RX_WINDOW_START moves to the next lowest SN of the ARQ block not yet received within the ARQ receiving window.
MAC Service Data Units (SDUs) are reconstructed from ARQ blocks in sequence. When a new ARQ block is received, the ARQ receiver checks if a complete SDU is able to be reconstructed. If it a complete SDU can be reconstructed, it is then transferred to an upper layer, otherwise, the ARQ block is buffered and the ARQ receiver waits for other ARQ blocks in order to reconstruct the SDU. When an ARQ block is skipped, ARQ blocks related to the reconstruction of the SDU are flushed from the buffer.
Both IEEE 802.16e and IEEE 802.16m support packing SDUs when forming a PDU, as well as fragmentation and reassembly. Herein, both variable and fixed length SDUs are supported by the IEEE 802.16e and IEEE 802.16m standards. More specifically, IEEE 802.16e defines a Fragmentation SubHeader (FSH) and a Packing SubHeader (PSH) to support variable length SDUs, examples of the format of which are shown below in Tables 1 and 2, respectively.
TABLE 1SizeSyntax(bit)NotesPacking Subheader( ){——FC 2Indicates the fragmentation state of thepayload:00 = no fragmentation01 = last fragmentation10 = first fragment11 = continuing (middle) fragmentif (ARQ-enabled Connection)——BSN11Sequence number of the first block in thecurrent SDU fragment.else {——if (Type bit Extended Type)——FSN11Sequence number of the current SDUfragment. The FSN value shall incrementby one (modulo 2048) for each fragment,including unfragmented SDUs andunpacked SDU or SDU fragments.else——FSN 3Sequence number of the current SDUfragment. The FSN value shall incrementby one (modulo 8) for each fragment,including unfragmented SDUs andunpacked SDU or SDU fragments.}——Length11Length of the SDU fragment inbytes including the PSH.}——
TABLE 2SizeSyntax(bit)NotesPacking Subheader( ){——FC2Indicates the fragmentation state of thepayload:00 = no fragmentation01 = last fragmentation10 = first fragment11 = continuing (middle) fragmentif (ARQ-enabled Connection)——BSN11 Sequence number of the first block in thecurrent SDU fragment.else {——if (Type bit Extended Type)——FSN11 Sequence number of the current SDUfragment. The FSN value shall incrementby one (modulo 2048) for each fragment,including unfragmented SDUs andunpacked SDU or SDU fragments.else——FSN3Sequence number of the current SDUfragment. The FSN value shall incrementby one (modulo 8) for each fragment,including unfragmented SDUs andunpacked SDU or SDU fragments.}——Reserved3Shall be set to zero.}——
Regarding Tables 1 and 2, FSH is substantially the same as PSH except the 11-bit “Length” field is replaced with a 3-bit “Reserved” field. FSH is used when the payload in a MAC PDU includes only one fragment SDU. This is why the “Length” field is not needed, because the generic MAC Header already has a length field. An example of variable-length SDUs packed into MAC PDUs including FSHs and PSHs based on IEEE 802.16e is described below with reference to FIG. 3.
FIG. 3 illustrates variable-length MAC SDUs packed into MAC PDUs including FSHs and PSHs according to the related art.
Regarding FIG. 3, r MAC SDUs 302, s−r+1 MAC PDUs 304, and t MAC SDUs 306 are shown. Each of the s−r+1 MAC PDUs 304 only has one SDU fragment and thus each SDU begins with one FSH. In contrast, the r MAC SDUs 302 and the t MAC SDUs 306 are each included in one MAC PDU that includes unfragmented SDUs and SDU fragments and therefore each SDU or SDU fragment begins with a PSH.
An ARQ receiver assembles MAC PDUs in order of the FSN, and uses a 2 bit Fragment Control (FC) field to divide the PDUs into groups and form SDUs. An SDU could be formed from just one data segment with an FC of “00”. Otherwise, an SDU is formed starting from one fragment with an FC of “10”, zero or more fragments with an FC of “11”, and ending with one fragment with an FC of “01”.
An example of packing fixed-length SDUs into a MAC PDU based on IEEE 802.16e is described below with reference to FIG. 4.
FIG. 4 illustrates fixed-length MAC SDUs packed into one MAC PDU according to the related art.
Regarding FIG. 4, k fixed-length MAC SDUs are packed into one MAC PDU, where an integer number of SDUs are packed one after the other. Given the length of the entire MAC PDU, the number of packed SDUs is equal to the length of the MAC PDU minus the MAC header, and divided by the pre-defined length of the SDU.
Another ARQ scheme according to the related art is found in 3rd Generation Partnership Project (3GPP) Evolved-Universal Mobile Telecommunications System (UMTS) Terrestrial Radio Access Network (E-UTRAN), a.k.a., Long Term Evolution (LTE). An example of a Radio Link Control (RLC) PDU structure is described below with reference to FIG. 5.
FIG. 5 illustrates an RLC PDU structure according to the related art.
Regarding FIG. 5, shown are SDUs of variable length, from which variable-length PDUs are formed. An LTE PDU (e.g., RLC PDU k) may consist of zero or one of the last fragment of the previous SDU (n), zero or more individual SDUs (e.g., n+1 and n+2), and zero or one of the first fragment of the next SDU (e.g., n+3). Alternatively, a PDU (e.g., RLC PDU) may consist of just one fragment in the middle of an SDU (e.g., n+3).
Herein, rather than using one FC field for each PSH as employed by the IEEE 802.16e and IEEE 802.16m standards, the RLC protocol utilized by the LTE standard uses a Framing Info (FI) field. If all PDUs arrive at the ARQ receiver successfully, the ARQ receiver may arrange the PDUs in the order of the SN, and find the start and end points of each SDU by checking the FI fields. The FI field is a 2-bit field that indicates whether an RLC SDU is segmented at the beginning and/or at the end of a data field. More specifically, the FI field indicates whether the first byte of the data field corresponds to the first byte of an RLC SDU, and whether the last byte of the data field corresponds to the last byte of an RLC SDU. The interpretation of the FI field is provided below in Table 3.
TABLE 3ValueDescription00First byte of the Data field corresponds to the first byte of a RLC SDU.Last byte of the Data field corresponds to the last byte of a RLC SDU.01First byte of the Data field corresponds to the first byte of a RLC SDU.Last byte of the Data field does not correspond to the last byte of a RLC SDU.10First byte of the Data field does not correspond to the first byte of a RLC SDU.Last byte of the Data field corresponds to the last byte of a RLC SDU.11First byte of the Data field does not correspond to the first byte of a RLC SDU.Last byte of the Data field does not correspond to the last byte of a RLC SDU.
An example of Unacknowledged Mode Data (UMD) is described below with reference to FIG. 6.
FIG. 6 illustrates a UMD PDU according to the related art.
Referring to FIG. 6, a UMD PDU with 5-bit SN is shown. Herein, the UMD PDU has an odd number of Length Indicator (LI) fields (i.e., K=1, 3, 5, etc.). The LI fields indicate the length in bytes of a corresponding data field element present in an RLC data PDU delivered/received by an Unacknowledged Mode (UM) entity or an Acknowledged Mode (AM) RLC entity. The first LI present in the RLC data PDU header corresponds to the first data field element present in the data field of the RLC data PDU, the second LI present in the RLC data PDU header corresponds to the second data field element present in the data field of the RLC data PDU, and so on. The value 0 for the LI field is reserved.
The SN field is 10 bits for an Acknowledged Mode Data (AMD) PDU, AMD PDU segments and STATUS PDUs, and is 5 bits or 10 bits (configurable) for a UMD PDU. The SN field indicates the sequence number of the corresponding UMD or AMD PDU. For an AMD PDU segment, the SN field indicates the sequence number of the original AMD PDU from which the AMD PDU segment was constructed from.
The Extension (E) bit field is a one bit field. The E field indicates whether a data field follows or a set of an E field and an LI field follows.
The ARQ operation employed by the LTE standard, known as AM Acknowledged Mode (AM), uses parameters that are different from those used by the IEEE 802.16e and IEEE 802.16m standards. More specifically, the ARQ transmitter uses a transmitting window that has three parameters, namely VT(A), VT(MS) and VT(S).
VT(A) is a state variable that holds the value of the SN of the next AMD PDU for which an ACK is to be received in-sequence, and it serves as the lower edge of the transmitting window. VT(A) is updated whenever the AM RLC entity receives an ACK for an AMD PDU with SN=VT(A).
VT(MS) is a state variable equal to VT(A)+AM_Window_Size, and it serves as the higher edge of the transmitting window.
VT(S) is a state variable that holds the value of the SN to be assigned for the next newly generated AMD PDU. VT(S) is updated whenever the AM RLC entity delivers an AMD PDU with SN=VT(S).
The ARQ receiver uses a receiving window that has five parameters, namely VR(R), VR(MR), VR(H), VR(MS), and VR(X).
VR(R) is a state variable that hold the value of the SN following the last in-sequence completely received AMD PDU, and it serves as the lower edge of the receiving window. VR(R) is updated whenever the AM RLC entity receives an AMD PDU with SN=VR(R).
VR(MR) is a state variable that equals VR(R)+AM_Window_Size, and it holds the value of the SN of the first AMD PDU that is beyond the receiving window and serves as the higher edge of the receiving window.
VR(H) is a state variable that holds the value of the SN following the SN of the RLC data PDU with the highest SN among received RLC data PDUs.
VR(MS) is a state variable that holds the highest possible value of the SN which can be indicated by “ACK_SN” when a STATUS PDU needs to be constructed.
VR(X) is a state variable that holds the value of the SN following the SN of the RLC data PDU which triggered T_reordering.
In a summary, IEEE 802.16e, IEEE 802.16m and LTE standards allow an ARQ transmitter to fragment packets coming from an upper layer in order to form an SDU. The fragmentation is indicated by the “FC” field in the IEEE 802.16e and IEEE 802.16m standards (see Tables 1 and 2) and the “FI” field in the LTE standard (see Table 3). Therefore, when an ARQ receiver has received an ARQ block with SN equal to the lower edge of the ARQ receiving window (i.e., ARQ_RX_WINDOW_START in IEEE 802.16e and IEEE 802.16m, and VR(R) in LTE), the ARQ receiver will advance the receiving window and transmit an ACK to the ARQ transmitter. However, this does not necessarily mean that the ARQ receiver can remove that ARQ block from the receiving buffer and deliver it to the upper layer, because a complete SDU has to first be formed.
For example, consider the scenario in FIG. 5. Here RLC PDU k−1 cannot be removed from the receiving buffer until RLC PDU k has also arrived because RLC SDU n cannot be reconstructed by RLC PDU k−1 itself. Similarly, RLC PDU k+1 cannot be removed from the receiving buffer until both RLC PDU k and RLC PDU k+2 have also arrived because RLC SDU n+3 cannot be reconstructed by RLC PDU k+1 itself. Thus, RLC PDU k+1 will have to wait for more RLC PDUs before being removed from the ARQ receiving buffer and delivered to the upper layer, depending on how RLC SDU n+3 was fragmented.
Accordingly, flow control is important when employing ARQ so that an ARQ transmitter does not overflow a buffer in an ARQ receiver. This issue is particularly important for wireless communication systems, where a Mobile Station (MS) typically has a limited buffer. Herein, buffer management is employed in the related art to address overflow a buffer in an ARQ receiver. Buffer management according to the related art is described below.
To facilitate buffer management, an ARQ receiver informs an ARQ transmitter of a maximum ARQ buffer size (ARQ_MAX_BUFFER_SIZE) during a capability negotiation. ARQ_MAX_BUFFER_SIZE is the maximum size of the ARQ buffer (in bytes) that the ARQ receiver is able to allocate for all ARQ connections. When there are one or more ARQ enabled flows for a given ARQ receiver, the ARQ transmitter maintains the state ARQ_BUFFER_USED, which is the total ARQ buffer usage of all ARQ enabled flows at the ARQ receiver, in addition to other per flow ARQ states. ARQ_BUFFER_USED accounts for all ARQ blocks and subblocks that have not yet been acknowledged in-order by the ARQ receiver. For example, if the ARQ transmitter sent blocks 0 to 10 and the ARQ receiver acknowledges blocks 1 to 10, the ARQ_BUFFER_USED shall consider PDUs with numbers 0 to 10 as occupying the AQR receiver's buffer. Once block 0 is also acknowledged, ARQ_BUFFER_USED is updated to indicate that blocks 0 to 10 have been cleared from the ARQ receiver's buffer. The ARQ transmitter ensures that the transmission or retransmission of ARQ blocks does not to exceed ARQ_MAX_BUFFER_SIZE−ARQ_BUFFER_USED.
However, one drawback with the buffer management of the related art is that an ARQ transmitter may still overflow the ARQ buffer in an ARQ receiver, because it assumes that all ARQ blocks (e.g., blocks 0 to 10) that have been accumulatively acknowledged by the ARQ receiver have been delivered to upper layer, and thus are no longer in the ARQ receiving buffer. However, this is not necessarily the case. Actually, an ARQ block which is a fragment of an MAC SDU cannot be delivered to upper layer until all the fragments have arrived at the ARQ receiver. In other words, an ARQ block may still be in the ARQ receiving buffer even if it is acknowledged by the ARQ receiver and the ARQ receiving window has moved beyond this ARQ block. Thus, the buffer management in the related art does not consider the SDU reconstruction issue, and thus the transmitter may overflow the ARQ buffer in an ARQ receiver.
Therefore, a need exists for techniques for advanced ARQ buffer management in a wireless communication system.